package com.ztom.top100;

/**
 * 不同的二叉搜索树
 * <p>
 * https://leetcode-cn.com/problems/unique-binary-search-trees/
 *
 * @author ZhangTao
 */
public class Code38NumTrees {

    public int numTrees2(int n) {
        if (n < 1) {
            return -1;
        }
        if (n == 1) {
            return 1;
        }

        return process(n);
    }

    /**
     * 以[1, n]各个位置的数作为根节点构建二叉搜索树
     * 左子树节点数: i - 1
     * 右子树节点数: n - i
     * 左右子树也必须是二叉搜索树, 相乘即可
     *
     * @param n
     * @return
     */
    private int process(int n) {
        if (n == 0 || n == 1) {
            return 1;
        }

        int ways = 0;
        // 以 i 位置的数作为根节点构建二叉搜索树
        for (int i = 1; i <= n; i++) {
            ways += process(i - 1) * process(n - i);
        }
        return ways;
    }

    public int numTrees(int n) {
        if (n < 1) {
            return -1;
        }
        int[] dp = new int[n + 1];
        dp[0] = 1;
        dp[1] = 1;

        // [1, n] 变化范围
        for (int i = 2; i <= n; i++) {
            // 以 i 位置的数作为根节点构建二叉搜索树
            for (int j = 1; j <= i; j++) {
                dp[i] += dp[j - 1] * dp[i - j];
            }
        }

        return dp[n];
    }
}
